package algorithms

import (
	"sort"
	"strings"
	"sync"
	"time"
)

// FastMap 高效的字符串映射，使用Trie树优化前缀搜索
type FastMap struct {
	mu   sync.RWMutex
	root *trieNode
	size int
}

type trieNode struct {
	children map[rune]*trieNode
	value    interface{}
	isEnd    bool
}

// NewFastMap 创建新的快速映射
func NewFastMap() *FastMap {
	return &FastMap{
		root: &trieNode{children: make(map[rune]*trieNode)},
	}
}

// Put 插入键值对，O(k)时间复杂度，k为键长度
func (fm *FastMap) Put(key string, value interface{}) {
	fm.mu.Lock()
	defer fm.mu.Unlock()
	
	node := fm.root
	for _, char := range key {
		if node.children[char] == nil {
			node.children[char] = &trieNode{children: make(map[rune]*trieNode)}
		}
		node = node.children[char]
	}
	
	if !node.isEnd {
		fm.size++
	}
	node.isEnd = true
	node.value = value
}

// Get 获取值，O(k)时间复杂度
func (fm *FastMap) Get(key string) (interface{}, bool) {
	fm.mu.RLock()
	defer fm.mu.RUnlock()
	
	node := fm.root
	for _, char := range key {
		if node.children[char] == nil {
			return nil, false
		}
		node = node.children[char]
	}
	
	return node.value, node.isEnd
}

// PrefixSearch 前缀搜索，返回所有匹配的键值对
func (fm *FastMap) PrefixSearch(prefix string) map[string]interface{} {
	fm.mu.RLock()
	defer fm.mu.RUnlock()
	
	result := make(map[string]interface{})
	node := fm.root
	
	// 找到前缀节点
	for _, char := range prefix {
		if node.children[char] == nil {
			return result
		}
		node = node.children[char]
	}
	
	// DFS收集所有子节点
	fm.collectKeys(node, prefix, result)
	return result
}

func (fm *FastMap) collectKeys(node *trieNode, prefix string, result map[string]interface{}) {
	if node.isEnd {
		result[prefix] = node.value
	}
	
	for char, child := range node.children {
		fm.collectKeys(child, prefix+string(char), result)
	}
}

// Size 返回映射大小
func (fm *FastMap) Size() int {
	fm.mu.RLock()
	defer fm.mu.RUnlock()
	return fm.size
}

// LRUCache 高效的LRU缓存实现
type LRUCache struct {
	mu       sync.RWMutex
	capacity int
	size     int
	cache    map[string]*cacheNode
	head     *cacheNode
	tail     *cacheNode
}

type cacheNode struct {
	key   string
	value interface{}
	prev  *cacheNode
	next  *cacheNode
	ttl   time.Time
}

// NewLRUCache 创建新的LRU缓存
func NewLRUCache(capacity int) *LRUCache {
	cache := &LRUCache{
		capacity: capacity,
		cache:    make(map[string]*cacheNode),
		head:     &cacheNode{},
		tail:     &cacheNode{},
	}
	cache.head.next = cache.tail
	cache.tail.prev = cache.head
	return cache
}

// Get 获取缓存值，O(1)时间复杂度
func (lru *LRUCache) Get(key string) (interface{}, bool) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	
	node, exists := lru.cache[key]
	if !exists {
		return nil, false
	}
	
	// 检查TTL
	if !node.ttl.IsZero() && time.Now().After(node.ttl) {
		lru.removeNode(node)
		delete(lru.cache, key)
		lru.size--
		return nil, false
	}
	
	// 移动到头部
	lru.moveToHead(node)
	return node.value, true
}

// Put 设置缓存值，O(1)时间复杂度
func (lru *LRUCache) Put(key string, value interface{}, ttl time.Duration) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	
	node, exists := lru.cache[key]
	if exists {
		node.value = value
		if ttl > 0 {
			node.ttl = time.Now().Add(ttl)
		}
		lru.moveToHead(node)
		return
	}
	
	newNode := &cacheNode{
		key:   key,
		value: value,
	}
	if ttl > 0 {
		newNode.ttl = time.Now().Add(ttl)
	}
	
	lru.cache[key] = newNode
	lru.addToHead(newNode)
	lru.size++
	
	if lru.size > lru.capacity {
		tail := lru.removeTail()
		delete(lru.cache, tail.key)
		lru.size--
	}
}

func (lru *LRUCache) addToHead(node *cacheNode) {
	node.prev = lru.head
	node.next = lru.head.next
	lru.head.next.prev = node
	lru.head.next = node
}

func (lru *LRUCache) removeNode(node *cacheNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (lru *LRUCache) moveToHead(node *cacheNode) {
	lru.removeNode(node)
	lru.addToHead(node)
}

func (lru *LRUCache) removeTail() *cacheNode {
	last := lru.tail.prev
	lru.removeNode(last)
	return last
}

// FastSort 高效排序算法集合
type FastSort struct{}

// QuickSort 优化的快速排序，使用三路划分处理重复元素
func (fs *FastSort) QuickSort(arr []string) {
	if len(arr) <= 1 {
		return
	}
	fs.quickSortRecursive(arr, 0, len(arr)-1)
}

func (fs *FastSort) quickSortRecursive(arr []string, low, high int) {
	if low < high {
		// 使用三路划分
		lt, gt := fs.threeWayPartition(arr, low, high)
		fs.quickSortRecursive(arr, low, lt-1)
		fs.quickSortRecursive(arr, gt+1, high)
	}
}

func (fs *FastSort) threeWayPartition(arr []string, low, high int) (int, int) {
	pivot := arr[low]
	lt := low
	gt := high
	i := low + 1
	
	for i <= gt {
		cmp := strings.Compare(arr[i], pivot)
		if cmp < 0 {
			arr[lt], arr[i] = arr[i], arr[lt]
			lt++
			i++
		} else if cmp > 0 {
			arr[i], arr[gt] = arr[gt], arr[i]
			gt--
		} else {
			i++
		}
	}
	
	return lt, gt
}

// BinarySearch 二分搜索，O(log n)时间复杂度
func (fs *FastSort) BinarySearch(arr []string, target string) int {
	left, right := 0, len(arr)-1
	
	for left <= right {
		mid := left + (right-left)/2
		cmp := strings.Compare(arr[mid], target)
		
		if cmp == 0 {
			return mid
		} else if cmp < 0 {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	
	return -1
}

// FuzzySearch 模糊搜索，使用编辑距离算法
func (fs *FastSort) FuzzySearch(arr []string, target string, maxDistance int) []string {
	var results []string
	
	for _, str := range arr {
		if fs.editDistance(str, target) <= maxDistance {
			results = append(results, str)
		}
	}
	
	// 按编辑距离排序
	sort.Slice(results, func(i, j int) bool {
		return fs.editDistance(results[i], target) < fs.editDistance(results[j], target)
	})
	
	return results
}

// editDistance 计算编辑距离（Levenshtein距离）
func (fs *FastSort) editDistance(s1, s2 string) int {
	m, n := len(s1), len(s2)
	dp := make([][]int, m+1)
	
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = i
	}
	
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
			}
		}
	}
	
	return dp[m][n]
}

func min(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	}
	if b < c {
		return b
	}
	return c
}